package com.fftf.algorithm.sort;

import java.util.Arrays;

/**
 * 优化后的冒泡排序
 *
 * @author qiancheng 18638109122@163.com
 * @desc
 * @create 2021/2/4 14:56
 */
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int cnt = 0;
        //检验非空数组
        if (arr.length <= 1) {
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            //定义flag 检验数组时候发生了交换
            boolean flag = false;
            int sortBorder=arr.length - 1;
            for (int j = i + 1; j < sortBorder; j++) {
                //定义临时变量
                int tmp = 0;
                if (arr[j] < arr[j-1]) {
                    tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                    //交换变量值 将flag置为true
                    flag = true;
                    sortBorder=j;
                }
                cnt++;
            }
            //如果循环一轮下来发现flag的值未变化，则数组已经有序，可以退出循环
            if (!flag) {
                System.out.println("数据不发生变化" + i);
                break;
            }
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 5, 4, 7, 8, 9, 10};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
